
//1930.长度为3的不同回文子序列
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int back[26]={0},prev[26]={0};  //使用数组统计前后分别存在那些字符
        unordered_set<string> st;  //st存储各种回文串
    
        int n=s.size();
        for(int i=2;i<n;i++) back[s[i]-'a']++;
        prev[s[0]-'a']++;

        for(int i=1;i<n-1;i++)
        {
            for(int j=0;j<26;j++)  //在左右两边查找出现的字符
            {
                if(back[j]&&prev[j])
                {
                    string tmp;
                    tmp+=char(j+'a');
                    tmp+=s[i];
                    st.insert(tmp);
                }
            }
            prev[s[i]-'a']++;    //将当前元素加入到prev数组
            back[s[i+1]-'a']--;      //将下一个元素移除back数组
        }
        return st.size();
    }
};